The present invention generally relates to implementation of a memory. More specifically, the invention is intended to be used in connection with all such memories that are based on a functional digital trie structure. The solution is, however, mainly intended for central memory databases. A functional structure denotes a memory in which updates, such as additions, are made in such a way that the path from the root to the point of addition is first copied, and the addition is made to the copied data (the addition is not made directly to the existing data). Such an updating procedure is also called by the term xe2x80x9ccopy-on-writexe2x80x9d.
The prior art unidimensional directory structure termed digital trie (the word xe2x80x9ctriexe2x80x9d is derived from the English word xe2x80x9cretrievalxe2x80x9d) is the underlying basis of the principle of the present invention. Digital trie structures can be implemented in two types: bucket tries, and tries having no buckets.
A bucket digital trie structure is a tree-shaped structure composed of two types of nodes: buckets and trie nodes. A bucket is a data structure that can accommodate a number of data units or a number of pointers to data units or a number of search key/data unit pairs or a number of search key/pointer pairs. A maximum size greater than one has been defined for said number. However, a bucket can contain a smaller number than said maximum number of data units, pointers, or key/pointer pairs, in which case the bucket is not full. A trie node, on the other hand, is an array guiding the retrieval, having a size of two by the power of k (2k) elements. If an element in a trie node is in use, it refers either to a trie node at the next level in the directory tree or to a bucket. In other cases, the element is free (empty).
Search in the database proceeds by examining the search key (which in the case of a subscriber database in a mobile telephone network or a telephone exchange, for instance, is typically the binary numeral corresponding to the telephone number of the subscriber) k bits at a time. The bits to be searched are selected in such a way that at the root level of the structure (in the first trie node), k leftmost bits are searched; at the second level of the structure, k bits next to the leftmost bits are searched, etc. The bits to be searched are interpreted as an unsigned binary integer that is employed directly to index the element table contained in the trie node, the index indicating a given element in the table. If the element indicated by the index is free, the search will terminate as unsuccessful. If the element refers to a trie node at the next level, k next bits extracted from the search key are searched at that level in the manner described above. As a result of comparison, the routine branches off in the trie node either to a trie node at the next level or to a bucket. If the element refers to a bucket containing a key, the key stored therein is compared with the search key. The entire search key is thus compared only after the search has encountered a bucket. Where the keys are equal, the search is successful, and the desired data unit is obtained at the storage address indicated by the pointer of the bucket. Where the keys differ, the search terminates as unsuccessful.
A bucketless trie structure has no buckets, but a leaf node containing only one element that can be a data unit, a pointer to a data unit, a search key/data unit pair or a search key/pointer pair corresponds to a bucket. In the present context, the nodes above the leaf nodes in the bucketless trie structure are called internal nodes; these correspond to trie nodes in a bucket structure (i.e., they comprise a similar table as trie nodes). In a bucketless digital trie structure, the nodes are thus either internal nodes or leaf nodes. By means of buckets, the need for reorganizing the directory structure can be postponed, as a large number of pointers, data units, search key/data unit pairs or search key/pointer pairs can be accommodated in the buckets until a time when such a need arises.
FIG. 1 shows an example of a digital trie structure in which the key has a length of 4 bits and k=2, and thus each trie node has 22=4 elements, and two bits extracted from the key are searched at each level. Leaves are denoted with references A, B, C, D . . . H . . . M, N, O and P. Thus a leaf is a node that does not point to a lower level in the tree. Internal nodes are denoted with references IN1 . . . IN5 and elements in the internal node with reference NE in FIG. 1.
In the exemplary case of FIG. 1, the search keys for the leaves shown are as follows: A=0000, B=0001, C=0010, . . . , H=0111, . . . and P=1111. In this case, a pointer is stored in each leaf to that storage location in the database SD at which the actual data, e.g. the telephone number of the pertinent subscriber and other information relating to that subscriber, is to be found. The actual subscriber data may be stored in the database for instance as a sequential file of the type shown in the figure. The search is performed on the basis of the search key of record H, for example, by first extracting from the search key the two leftmost bits (01) and interpreting them, which delivers the second element of node IN1, containing a pointer to node IN3 at the next level. At this level, the two next bits (11) are extracted from the search key, thus yielding the fourth element of that node, pointing to record H.
Instead of a pointer, a leaf may contain (besides a search key) an actual data file (also called by the more generic term data unit). Thus for example the data relating to subscriber A (FIG. 1) may be located in leaf A, the data relating to subscriber B in leaf B, etc.
The present invention mainly relates to bucketless trie structures, since the solution in accordance with the invention affords the same advantages as a bucket structure, and thus the invention yields greater benefit in bucketless structures. These facts will be described in detail hereinafter.
The search key may also be multidimensional. In other words, the search key may comprise a number of attributes (for example the family name and one or more forenames of a subscriber). Such a multidimensional trie structure is disclosed in international application No. PCT/FI95/00319 (published under number WO 95/34155). In said structure, address computation is performed in such a way that a given predetermined number of bits at a time is selected from each dimension independently of the other dimensions. Hence, a fixed limit independent of the other dimensions is set for each dimension in any individual node of the trie structure, by predetermining the number of search key bits to be searched in each dimension. With such a structure, the memory circuit requirement can be curbed when the distribution of the values of the search keys is known in advance, in which case the structure can be implemented in a static form.
If the possibility of reorganizing the structure in accordance with the current key distribution to be optimal in terms of efficiency and storage space occupancy is desired, the size of the nodes must vary dynamically as the key distribution changes. When the key distribution is even, the node size may be increased to make the structure flatter (a flatter structure entails faster retrievals). On the other hand, with uneven key distributions in connection with which storage space occupancy will present a problem in memory structures employing dynamic node size, the node size can be maintained small, which will enable locally a more even key distribution and thereby smaller storage space occupancy. Dynamic changes of node size require the address computation to be implemented in such a way that in each node of the tree-shaped hierarchy constituted by the digital trie structure, a node-specific number of bits is selected from the bit string constituted by the search keys used. Dynamic reorganizing of the nodes naturally requires part of the processing capacity.
The choice between a fixed node size and a dynamically changing node size is dependent for example on what type of application the memory is intended for, e.g. what the number of database searches, additions and deletions is and what the proportions of said operations are.
The efficiency and performance of the memory are thus influenced, among other things, by the storage space required by the trie structure and the depth of the trie structure. In a functional digital trie structure, in which the entire search path from the root to the point of updating has to be copied in connection with updates, the performance of the memory is also influenced by how many words to be copied such a path contains. Thus, if compression is performed in the memory, this should be done in such a way that the quantity of data to be copied does not increase as a result of compression to such an extent as to impair the performance of the memory.
U.S. Pat. No. 5,276,868 discloses a compression method for a trie node. This system supports only two node sizes: quads and nodes of size 16. In the method, some of the nil pointers are removed from the nodes in such a way that nodes having less than five non-nil pointers are converted to compressed quads, whereas the remaining nodes are maintained uncompressed. The structure thus includes both compressed nodes and non-compressed nodes of size 16. Since nil pointers must still be stored in the structure, the structure does not provide a very good result in view of storage space requirement and copying costs. Also, since only two node sizes are possible, the structure is not well suited to functional memories or other memories having efficient memory management that is capable of allocating memory for use a single word at a time.
Hence, the problem with a functional trie structure is how compression should be carried out in the structure in order for the memory performance to be as good as possible, observing all the above factors.
It is an object of the present invention to provide a solution to the problem described above. This object is achieved with the method defined in the independent claims.
The invention makes use of the prior art width compression, to which reference is made e.g. in the above U.S. Patent. For this reason, the node size for the trie tree is already initially selected to be as large as possible: the logical size of the nodes used in the structure is preferably 16, but can in principle be even greater. In accordance with the invention, increasing the width-compressed node is permitted up to a maximum limit, which is smaller than the maximum size of the node. The node is split into a cluster of nodes as soon as it grows to be in excess of this threshold value. In the case of a width-compressed node having 16 elements, for example, it is preferred to employ 13 child nodes as the threshold value. If the number of child nodes exceeds 13, the parent node is disassembled into a cluster of compressed quad nodes.
The idea in accordance with the invention is based on the insight that as the size of a width-compressed node increases, the copying costs increase sharply at some stage, since the copying carried out in connection with updates always takes place from the root of the tree up to the point of update and since the nodes in the upper part of the tree, which are copied at every copying round, are filled first and are normally fuller than the lower nodes. Hence, increasing the fill rate of a width-compressed node is of no avail when a certain stage has been reached, but the increase in copying costs totally eliminates the advantage to be gained with width compression. In accordance with the invention, at this stage at the latest the width-compressed node is converted back to a cluster of nodes at two different hierarchy levels.
The idea is also to avoid such a sharp increase in copying costs, so that the cluster of nodes to be formed is as advantageous as possible in view of the requirements set out above. For example, the threshold value 13 stated above is advantageous for nodes of size 16 in the sense that the copying costs cannot increase sharply yet, and on the other hand, when the size is greater than 13, one can be certain that when a cluster of quad nodes is formed, the parent node will contain no nil pointers. Hence, the search operation can be accelerated, since the number of pointers in said node need not be examined in connection with the search. Furthermore, one can be certain that in the node cluster to be formed, none of the child nodes in the cluster will be path-compressed (it is preferable to use path compression in the structure), since in this case the parent node is full and each child node has at least two child nodes (the path compression to be carried out in the quad cluster will retard the calculation).
In order for the memory performance to remain optimum the entire time, it is preferable to reassemble the cluster of nodes into a width-compressed node when the number of the grandchild nodes of the parent node of the cluster falls to said threshold value or below it.
When the solution in accordance with the invention is used, the memory consumption of the functional structure can be diminished by means of width compression without the number of words to be copied in connection with updates substantially increasing and thereby diminishing the advantage to be gained by width compression.